package com.zjoin.study.arithmetic.进阶;

import java.util.Arrays;

/**
 * 类名 动态规划
 * 描述
 *
 * @Author xwyang
 * @Date 2020/8/11 14:31
 * @Version 1.0
 **/
public class 动态规划 {
    
    public static void main(String[] args) {
        int[] coins = {2, 5, 8};
        int amount = 13;

//        long t1 = System.currentTimeMillis();
//        for (int i = 0; i < amount; i++) {
//            System.out.print(sample1(coins, i) + " ");
//        }
//        long t2 = System.currentTimeMillis();
//        System.out.println();
//        for (int i = 0; i < amount; i++) {
//            System.out.print(sample2(coins, i) + " ");
//        }
//        long t3 = System.currentTimeMillis();
//        System.out.println();
//        for (int i = 0; i < amount; i++) {
//            System.out.print(sample3(coins, i) + " ");
//        }
//        long t4 = System.currentTimeMillis();
//        System.out.println();
//        for (int i = 0; i < amount; i++) {
//            System.out.print(sample4(coins, i) + " ");
//        }
//        long t5 = System.currentTimeMillis();
//        System.out.println();
//        System.out.println("耗时分别为：" + (t2 - t1) + "," + (t3 - t2) + "," + (t4 - t3) + "," + (t5 - t4));

//        System.out.println(recursion(coins, amount));
        System.out.println(sample3(coins, amount));
    }
    
    /**
     * 凑钱问题
     * 描述：给定硬币面额数组，比如 [1、2、5] 三种面额的可选金额，凑成目标金额，比如：10
     * 问题：最少需要多少不同面额的硬币？
     */
    
    /**
     * 递归
     *
     * @param coins  面额数组
     * @param amount 目标金额
     * @return
     */
    public static int recursion(int[] coins, int amount) {
        int[] ans = {Integer.MAX_VALUE};
        recursion(coins, amount, 0, ans);
        return ans[0] == Integer.MAX_VALUE ? -1 : ans[0];
    }
    
    private static void recursion(int[] coins, int amount, int count, int[] ans) {
    
        // 如果剩余金额 小于 0 此路不同，返回 遍历下一种面额
        if (amount < 0) {
            return;
        }
        if (amount == 0) {
            ans[0] = Math.min(ans[0], count);
        }
        // 如果剩余金额 等于 0
        //  取缓存在ans中的硬币数 和 当前组合所需硬币数 中最小的那个 作为最新所需硬币数
        for (int i = 0; i < coins.length; i++) {
            //按顺序遍历 目标金额 - 不同面额 所需硬币数
            System.out.print("[" + (amount - coins[i]) + "  " + Math.min(ans[0], count + 1) + " ] ");
            recursion(coins, amount - coins[i], count + 1, ans);
            System.out.println();
        }
        /**
         * 遍历过程
         *
         * [11  1 ] [9  2 ] [7  3 ] [5  4 ] [3  5 ] [1  6 ] [-1  7 ]
         *                                                  [-4  7 ]
         *                                                  [-7  7 ]
         *
         *                                  [-2  6 ]
         *                                  [-5  6 ]
         *
         *                          [0  5 ] [-2  5 ]
         *                                  [-5  5 ]
         *                                  [-8  5 ]
         *
         *                          [-3  5 ]
         *
         *                  [2  4 ] [0  5 ] [-2  5 ]
         */
        
        /**
         * [-5  5 ]
         * [-8  5 ]
         *
         * [-3  5 ]
         * [-6  5 ]
         *
         * [-1  4 ]
         *
         * [4  3 ] [2  4 ] [0  5 ] [-2  5 ]
         * [-5  5 ]
         * [-8  5 ]
         *
         * [-3  5 ]
         * [-6  5 ]
         *
         * [-1  4 ]
         * [-4  4 ]
         *
         * [1  3 ] [-1  4 ]
         * [-4  4 ]
         * [-7  4 ]
         *
         *
         * [6  2 ] [4  3 ] [2  4 ] [0  5 ] [-2  5 ]
         * [-5  5 ]
         * [-8  5 ]
         *
         * [-3  5 ]
         * [-6  5 ]
         *
         * [-1  4 ]
         * [-4  4 ]
         *
         * [1  3 ] [-1  4 ]
         * [-4  4 ]
         * [-7  4 ]
         *
         * [-2  3 ]
         *
         * [3  2 ] [1  3 ] [-1  4 ]
         * [-4  4 ]
         * [-7  4 ]
         *
         * [-2  3 ]
         * [-5  3 ]
         *
         *
         * [8  1 ] [6  2 ] [4  3 ] [2  4 ] [0  5 ] [-2  5 ]
         * [-5  5 ]
         * [-8  5 ]
         *
         * [-3  5 ]
         * [-6  5 ]
         *
         * [-1  4 ]
         * [-4  4 ]
         *
         * [1  3 ] [-1  4 ]
         * [-4  4 ]
         * [-7  4 ]
         *
         * [-2  3 ]
         *
         * [3  2 ] [1  3 ] [-1  4 ]
         * [-4  4 ]
         * [-7  4 ]
         *
         * [-2  3 ]
         * [-5  3 ]
         *
         * [0  2 ] [-2  2 ]
         * [-5  2 ]
         * [-8  2 ]
         *
         *
         * [5  1 ] [3  2 ] [1  2 ] [-1  2 ]
         * [-4  2 ]
         * [-7  2 ]
         *
         * [-2  2 ]
         * [-5  2 ]
         *
         * [0  2 ] [-2  2 ]
         * [-5  2 ]
         * [-8  2 ]
         *
         * [-3  2 ]
         *
         *
         */
        
    }
    
    
    /**
     * 记忆化搜索
     *
     * @param coins  面额数组
     * @param amount 目标金额
     * @return
     */
    public static int memorizedSearch(int[] coins, int amount) {
        if (amount <= 0) {
            return 0;
        }
        //新增金额大小的数组，用于存储每种金额所需的最少硬币个数，初始化都是0
        return memorizedSearch(coins, amount, new int[amount]);
    }
    
    private static int memorizedSearch(int[] coins, int amount, int[] ans) {

        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        System.out.println("\n计算金额[ " + amount + " ] ");
        //如果【当前金额-1】所需的硬币数已经计算过，直接取出来即可，不再重复计算
        if (ans[amount - 1] != 0) {
            System.out.println("      金额 [ " + amount + " ]【已计算】");
            return ans[amount - 1];
        }
        int res = Integer.MAX_VALUE;
        //循环当前余额 - 每种面额
        for (int c : coins) {
            int remain = amount - c;
            System.out.print("   [" + amount + "-" + c + "=" + remain + "");
            if (remain < 0) {
                System.out.print("，跳过]");
            } else if (remain == 0) {
                System.out.print("，得解]");
            } else {
                System.out.print("，继续]");
            }
            int sub = memorizedSearch(coins, remain, ans);
            if (sub == -1) {
                continue;
            }
            res = Math.min(res,
                    sub + 1);
        }
        System.out.println();
        res = res == Integer.MAX_VALUE ? -1 : res;
        ans[amount - 1] = res;
        return res;
        
        /** 遍历过程
         *
         * 计算金额[ 13 ]
         *    [13-2=11，继续]
         * 计算金额[ 11 ]
         *    [11-2=9，继续]
         * 计算金额[ 9 ]
         *    [9-2=7，继续]
         * 计算金额[ 7 ]
         *    [7-2=5，继续]
         * 计算金额[ 5 ]
         *    [5-2=3，继续]
         * 计算金额[ 3 ]
         *    [3-2=1，继续]
         * 计算金额[ 1 ]
         *    [1-2=-1，跳过]   [1-5=-4，跳过]   [1-8=-7，跳过]
         *    [3-5=-2，跳过]   [3-8=-5，跳过]
         *    [5-5=0，得解]   [5-8=-3，跳过]
         *    [7-5=2，继续]
         * 计算金额[ 2 ]
         *    [2-2=0，得解]   [2-5=-3，跳过]   [2-8=-6，跳过]
         *    [7-8=-1，跳过]
         *    [9-5=4，继续]
         * 计算金额[ 4 ]
         *    [4-2=2，继续]
         * 计算金额[ 2 ]
         *       金额 [ 2 ]【已计算】
         *    [4-5=-1，跳过]   [4-8=-4，跳过]
         *    [9-8=1，继续]
         * 计算金额[ 1 ]
         *       金额 [ 1 ]【已计算】
         *
         *    [11-5=6，继续]
         * 计算金额[ 6 ]
         *    [6-2=4，继续]
         * 计算金额[ 4 ]
         *       金额 [ 4 ]【已计算】
         *    [6-5=1，继续]
         * 计算金额[ 1 ]
         *       金额 [ 1 ]【已计算】
         *    [6-8=-2，跳过]
         *    [11-8=3，继续]
         * 计算金额[ 3 ]
         *       金额 [ 3 ]【已计算】
         *
         *    [13-5=8，继续]
         * 计算金额[ 8 ]
         *    [8-2=6，继续]
         * 计算金额[ 6 ]
         *       金额 [ 6 ]【已计算】
         *    [8-5=3，继续]
         * 计算金额[ 3 ]
         *       金额 [ 3 ]【已计算】
         *    [8-8=0，得解]
         *    [13-8=5，继续]
         * 计算金额[ 5 ]
         *       金额 [ 5 ]【已计算】
         *
         * 2
         *
         * Process finished with exit code 0
         */
    }
    
    public static int dp(int[] coins, int amount) {
        /**
         *  题解：
         *      1、当目标金额 < 0 时，无解；
         *      2、当目标金额 = 0 时，结果为 0 ；
         *      3、当目标金额 > 0 时：
         *           假设目标金额为 m ，计算方程为 dp(m)。
         *              那我们只要计算dp(m)=【min(dp(m-1),dp(m-2),dp(m-5))+1】即可
         *
         */
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        //金额从1开始
        for (int i = 1; i <= amount; i++) {
            //每中目标金额，最多计算 coins.length 次数，
            //  因为即便目标金额远大于可选面额，那在计算当前金额之前，比较计算过了m-1、m-2、m-5
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    //dp[i]初始化了每种目标金额所需的最大硬币数
                    /**
                     * 假定目标金额为10
                     * 那么只要知道 当目标金额为 9、8、5 时所需硬币数最少的那个 +1 即可；
                     * 目标金额为 9、8、5 已经计算过，直接通过下标取出
                     */
    
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
        /**遍历过程
         *
         * 计算金额 [ 1 ] 当前dp[1]=14
         *     面额2 > 金额1，跳过
         *     面额5 > 金额1，跳过
         *     面额8 > 金额1，跳过
         * 计算金额 [ 2 ] 当前dp[2]=14
         *     面额2 <= 金额2，取dp[2] 和 dp[0]+1的最小值，dp[2]=1
         *     面额5 > 金额2，跳过
         *     面额8 > 金额2，跳过
         * 计算金额 [ 3 ] 当前dp[3]=14
         *     面额2 <= 金额3，取dp[3] 和 dp[1]+1的最小值，dp[3]=14
         *     面额5 > 金额3，跳过
         *     面额8 > 金额3，跳过
         * 计算金额 [ 4 ] 当前dp[4]=14
         *     面额2 <= 金额4，取dp[4] 和 dp[2]+1的最小值，dp[4]=2
         *     面额5 > 金额4，跳过
         *     面额8 > 金额4，跳过
         * 计算金额 [ 5 ] 当前dp[5]=14
         *     面额2 <= 金额5，取dp[5] 和 dp[3]+1的最小值，dp[5]=14
         *     面额5 <= 金额5，取dp[5] 和 dp[0]+1的最小值，dp[5]=1
         *     面额8 > 金额5，跳过
         * 计算金额 [ 6 ] 当前dp[6]=14
         *     面额2 <= 金额6，取dp[6] 和 dp[4]+1的最小值，dp[6]=3
         *     面额5 <= 金额6，取dp[6] 和 dp[1]+1的最小值，dp[6]=3
         *     面额8 > 金额6，跳过
         * 计算金额 [ 7 ] 当前dp[7]=14
         *     面额2 <= 金额7，取dp[7] 和 dp[5]+1的最小值，dp[7]=2
         *     面额5 <= 金额7，取dp[7] 和 dp[2]+1的最小值，dp[7]=2
         *     面额8 > 金额7，跳过
         * 计算金额 [ 8 ] 当前dp[8]=14
         *     面额2 <= 金额8，取dp[8] 和 dp[6]+1的最小值，dp[8]=4
         *     面额5 <= 金额8，取dp[8] 和 dp[3]+1的最小值，dp[8]=4
         *     面额8 <= 金额8，取dp[8] 和 dp[0]+1的最小值，dp[8]=1
         * 计算金额 [ 9 ] 当前dp[9]=14
         *     面额2 <= 金额9，取dp[9] 和 dp[7]+1的最小值，dp[9]=3
         *     面额5 <= 金额9，取dp[9] 和 dp[4]+1的最小值，dp[9]=3
         *     面额8 <= 金额9，取dp[9] 和 dp[1]+1的最小值，dp[9]=3
         * 计算金额 [ 10 ] 当前dp[10]=14
         *     面额2 <= 金额10，取dp[10] 和 dp[8]+1的最小值，dp[10]=2
         *     面额5 <= 金额10，取dp[10] 和 dp[5]+1的最小值，dp[10]=2
         *     面额8 <= 金额10，取dp[10] 和 dp[2]+1的最小值，dp[10]=2
         * 计算金额 [ 11 ] 当前dp[11]=14
         *     面额2 <= 金额11，取dp[11] 和 dp[9]+1的最小值，dp[11]=4
         *     面额5 <= 金额11，取dp[11] 和 dp[6]+1的最小值，dp[11]=4
         *     面额8 <= 金额11，取dp[11] 和 dp[3]+1的最小值，dp[11]=4
         * 计算金额 [ 12 ] 当前dp[12]=14
         *     面额2 <= 金额12，取dp[12] 和 dp[10]+1的最小值，dp[12]=3
         *     面额5 <= 金额12，取dp[12] 和 dp[7]+1的最小值，dp[12]=3
         *     面额8 <= 金额12，取dp[12] 和 dp[4]+1的最小值，dp[12]=3
         * 计算金额 [ 13 ] 当前dp[13]=14
         *     面额2 <= 金额13，取dp[13] 和 dp[11]+1的最小值，dp[13]=5
         *     面额5 <= 金额13，取dp[13] 和 dp[8]+1的最小值，dp[13]=2
         *     面额8 <= 金额13，取dp[13] 和 dp[5]+1的最小值，dp[13]=2
         */
    
    
    public static int sample3(int[] coins, int amount) {
        int[] ans = new int[1];
        ans[0] = 1 << 31 - 1;
        dfs(amount, coins, coins.length - 1, 0, ans);
        
        return ans[0] == 1 << 31 - 1 ? -1 : ans[0];
    }
    
    public static void dfs(int amount, int[] coins, int c_index, int times, int[] ans) {
        
        if (amount == 0) {
            ans[0] = Math.min(ans[0], times);
        }
        if (c_index < 0) {
            System.out.println("没有更小的面额，跳过");
            return;
        }
        System.out.println("计算金额[ " + amount + " ]");
        /**
         * 贪心策略
         *      要想硬币数最少，那就取最大面额硬币的极值
         *      比如 面额为【2、5】，目标金额为 36
         *      能取的面额最大的硬币数为 36%5=7……1
         *      剩余1 无法凑成
         */
        
        int k = amount / coins[c_index];
        
        /**
         * dfs剪枝
         * 只有当
         *      k - 是当前最大面额能取得的最大硬币数
         *      times - 以往最大面额可取硬币最大数之和
         *      如果 k+times >=已有组合的做大硬币数，则不是目标解，无需继
         *
         */
        System.out.println("    取硬币个数k=" + k + ", 已取次数times=" + times);
        if (k + times >= ans[0]) {
            System.out.println("\n跳过取 " + k + " 个 " + coins[c_index] + " 的组合，因为所需硬币数最小值 >= " + ans[0] + " ");
        }
        
        for (int i = k; i >= 0 && k + times < ans[0]; i--) {
            int remain = amount - coins[c_index] * i;
            if (remain == 0) {
                System.out.println("取" + i + "个" + coins[c_index] + "剩余金额：" + remain + ",找到目标解");
            } else {
                System.out.println("取" + i + "个" + coins[c_index] + "剩余金额：" +
                        "" + remain + ",继续下一个面额 " + coins[c_index - 1] + " 取值的可能性");
            }
            
            dfs(remain, coins, c_index - 1, times + i, ans);
        }
        /**
         * 计算金额[ 13 ]
         *     取硬币个数k=1, 已取次数times=0
         * 取1个8剩余金额：5,继续下一个面额 5 取值的可能性
         * 计算金额[ 5 ]
         *     取硬币个数k=1, 已取次数times=1
         * 取1个5剩余金额：0,找到目标解
         * 计算金额[ 0 ]
         *     取硬币个数k=0, 已取次数times=2
         *
         * 跳过取 0 个 2 的组合，因为所需硬币数最小值 >= 2
         * 取0个8剩余金额：13,继续下一个面额 5 取值的可能性
         * 计算金额[ 13 ]
         *     取硬币个数k=2, 已取次数times=0
         *
         * 跳过取 2 个 5 的组合，因为所需硬币数最小值 >= 2
         */
    }
    
    
    public static int sample4(int[] coins, int amount) {
        Arrays.sort(coins);
        int[] ans = {Integer.MAX_VALUE};
        dfs(coins, coins.length - 1, amount, 0, ans);
        return ans[0] == Integer.MAX_VALUE ? -1 : ans[0];
    }
    
    public static void dfs(int[] coins, int index, int amount, int cnt, int[] ans) {
        if (index < 0) {
            return;
        }
        for (int c = amount / coins[index]; c >= 0; c--) {
            int remain = amount - c * coins[index];
            int ncnt = cnt + c;
            if (remain == 0) {
                ans[0] = Math.min(ans[0], ncnt);
                break;//剪枝1
            }
            if (ncnt + 1 >= ans[0]) {
                break; //剪枝2
            }
            dfs(coins, index - 1, remain, ncnt, ans);
        }
    }
    
    
}
